package algorithm_demo.demo03;

/**
 * 二叉树中最大的二叉搜索子树
 * 给定一棵二叉树的头节点head，返回这颗二叉树中最大的二叉搜索子树的大小
 * @author Api
 * @date 2023/2/12 16:01
 */
public class Code05_MaxSubBSTSize {
    private static class Node {
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    public static int maxSubBSTSize(Node head){
        if (head == null){
            return 0;
        }
        return process(head).maxBSTSubSize;
    }


    public static Info process(Node x){
        if (x == null){
            return null;
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        int allSize = 1;
        int max = x.value;
        int min = x.value;
        if (leftInfo != null){
            max = Math.max(max, leftInfo.max);
            min = Math.min(min, leftInfo.min);
            allSize+= leftInfo.allSize;
        }

        if (rightInfo != null){
            max = Math.max(max, rightInfo.max);
            min = Math.min(min, rightInfo.min);
            allSize+= rightInfo.allSize;
        }
        int p1 = -1;
        if (leftInfo != null){
            p1 = leftInfo.maxBSTSubSize;
        }
        int p2 = -1;
        if (rightInfo != null){
            p2 = rightInfo.maxBSTSubSize;
        }

        int p3 = -1;
        //左边是否为二叉搜索树
        boolean leftBST = leftInfo == null || (leftInfo.maxBSTSubSize == leftInfo.allSize);
        //右边是否为二叉搜索树
        boolean rightBST = rightInfo == null || (rightInfo.maxBSTSubSize == rightInfo.allSize);
        //左右两边都是二叉搜索树
        if (leftBST && rightBST){
            boolean leftMaxLessX = leftInfo == null || (leftInfo.max < x.value);
            boolean rightMinMostX = rightInfo == null || (rightInfo.min > x.value);
            if (leftMaxLessX && rightMinMostX){
                int leftSize = leftInfo == null? 0:leftInfo.allSize;
                int rightSize = rightInfo == null? 0: rightInfo.allSize;
                p3 = leftSize+rightSize+1;
            }
        }
        int maxBSTSubSize = Math.max(p1, Math.max(p2, p3));
        return new Info(max, min, maxBSTSubSize, allSize);
    }

    public static class Info{
        public int max;
        public int min;
        public int maxBSTSubSize;
        public int allSize;

        public Info(int max, int min, int maxBSTSubSize, int allSize){
            this.max = max;
            this.min = min;
            this.maxBSTSubSize = maxBSTSubSize;
            this.allSize = allSize;
        }
    }
}
